package com.leetcode.twoPoint;

//接雨水
public class lc_42 {
    public static void main(String[] args) {

    }

    //给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。
    public static int trap(int[] height) {
        if(height == null || height.length == 0){
            return 0;
        }
        int left = 0, right = height.length - 1;
        int maxLeft = 0, maxRight = 0;
        int water = 0;

        while(left < right){
            //核心思路: 1.逐次计算单个桶的蓄水量, water(蓄水量) = max(木桶容量) - height(单个桶下方方块)
            //2.在逐次遍历的过程中,我们可以确定较小的前缀(比如左边前缀较小)那边的木桶的容量==这个较小的前缀
            //因为我们知道右边的前缀更大,水不会因为右边而变多变少,只需要考虑左边这个较小的前缀,这样就计算出了桶的容量
            //逐次遍历,计算出左边最大值和右边最大值
            maxLeft = Math.max(maxLeft,height[left]);
            maxRight = Math.max(maxRight,height[right]);
            //当左边最大值(左边最大前缀小于右边最大前缀) 单个木桶容量由左边决定 蓄水量=容量-高度
            //计算完成之后让left往右遍历继续获取最大前缀
            if (maxLeft < maxRight){
                water += maxLeft - height[left];
                left++;
            }else {
                //右边最大前缀小于左边最大前缀时,单个木桶的容量由右边决定 蓄水量=容量-高度
                //计算完成之后让right往左遍历继续获取最大前缀
                water += maxRight - height[right];
                right--;
            }
        }
        return water;
    }
}
